如果没有不能走到的点，这道题就非常简单了。我们只需向下走步，向右走步，就可到达右下角。在这步中，我们选向下走，那么答案为。
但是，棋盘中有些点是不能走的，我们考虑用容斥原理去除多余方案，即
CF167E Wizards and Bets
首先，我们将所有源点与汇点筛出来，然后从每一个源点dfs求出它到各汇点的路径数，题目中保证源点与汇点数量相同，我们记为。
那么，我们可以得到一个的矩阵。
先考虑路径不相交的情况（似乎大家思路都是这样），题目求的是一个排列的逆序对数，记为。那么，题目等价于求：
P1769 淘汰赛制
与题目定义有些不同，表示人数，表示淘汰赛轮数。题目显然输入的是,根据它算出。为了方便2进制计算，编号从~。最后答案加1即可。同时，比赛胜败概率为了方便先除以100，用计算。
现在考虑如何计算答案，设为对的胜率，为第轮胜出的概率。那么有：
CF147B Smile House
貌似 @DDF_Van 大佬的标程过不了 ， 有些题解用的二分会多一个，那就补一发倍增题解吧。
Solution 1
设表示走了不多于条边，的最大边权(走不通为极小值)
P2146 [NOI2015]软件包管理器
这其实是一道树链剖分的板题，难在读题...
借一下洛谷的图：（将边看成无向的）
P3704 [SDOI2017]数字表格
前置知识：莫比乌斯反演，数论分块
题意
P2922 秘密消息
这道题还是树的板题，先将个信息插入字典树中，对于查询的密码，在字典树中查询即可。
插入很好办，我们现在来讨论查询操作。我们记为任意一个信息，是待匹配的密码。表示有多少个字符串经过点，表示有多少个字符串以点结尾。
那么会出现三种情况：
P3119 Grass Cownoisseur
我们应该用缩点，将原图变为图，同时记录每个强连通分量的节点个数，记为。
因为起点终点都是1，所以路径一定是一个环。我们可以处理出1到所有点的距离，存在中（跑正图）和所有点到1的距离存在中（跑反图）。注意，如果走不到就设为极小值。最短路跑的是点权，其实和边权差不多。
题目说可以逆向走一条有向边，我们设该边起点为，终点为，那么，答案就应为。
P2341 [HAOI2006]受欢迎的牛
这道题一看就是一道强连通分量的题，不会的可以参考我的博客。
当我们用缩点之后，记新图点的个数为。我们枚举原图的每一条边，计算新图中的点的出度。对于点，我们把它的出度记为。那么，会有以下几种情况：
1.没有一个为0，说明每一个点至少有一条连向其他边的有向边，那么新图至少有条边，一定会有一个环(因为条边是一棵树，无论如何加边都会构成环)，但缩点后不可能有环，矛盾。